package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-10-02 15:51
 */

/**
 * 题目:
 * 给定循环升序列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
 * 给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
 * 如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
 * 如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
 */
public class Test42_排序的循环链表 {
    class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }

    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        if (head == null) {
            node.next = node;
            return node;
        }
        Node cur = head;
        while (cur.val <= cur.next.val) {
            cur = cur.next;
            if (cur == head) {
                break;
            }
        }
        if (node.val <= cur.next.val || node.val >= cur.val) {
            node.next = cur.next;
            cur.next = node;
            return head;
        }
        cur = cur.next;
        while (node.val > cur.next.val) {
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
        return head;
    }
}
